package stru1.day3;

import java.util.*;

/**
 * 350. 两个数组的交集 II
 */
public class Solution1 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(intersect(new int[]{1, 2, 2, 1}, new int[]{2, 2})));
        System.out.println(Arrays.toString(intersect(new int[]{4, 9, 5}, new int[]{9, 4, 9, 8, 4})));
    }

    /**
     * 利用哈希表计数
     * 时间复杂度 O(m+n)
     * 空间复杂度 O(min(m,n)) 当然本方法不是，因为没有比较nums1和nums2长度来保证map的大小较小
     */
    public static int[] intersect(int[] nums1, int[] nums2) {
        //统计nums1中各数字出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums1) {
            if (map.containsKey(i)) {
                map.put(i, map.get(i) + 1);
            } else {
                map.put(i, 1);
            }
        }

        //遍历nums2，查找map是否有，若有则输出
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int i : nums2) {
            if (map.containsKey(i) && map.get(i) != 0) {
                map.put(i, map.get(i) - 1);
                intersection[index++] = i;
            }
        }

        return Arrays.copyOfRange(intersection, 0, index);
    }

    /**
     * 如果数组是有序的，则用双指针
     * 时间复杂度 O(mlogm+nlogn)两次排序的消耗，若数组已经排序好，则为O(min(m,n))
     * 空间复杂度 O(min(m,n)) 当然本方法不是，因为没有比较nums1和nums2长度来保证答案数组的大小较小
     */
    public static int[] intersect1(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int[] intersection = new int[nums1.length];
        int index = 0;
        int i = 0, j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] > nums2[j]) {
                j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                intersection[index++] = nums1[i];
                i++;
                j++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}
